/**********************************************************************
**	Authors: Erik Sapir & Lior Zibi

**
**  Lock-free List based on M. Michael's algorithm.
**
**
**********************************************************************/


#ifndef __LOCK_FREE_LIST__H
#define __LOCK_FREE_LIST__H

#include "framework/cpp_framework.h"
#include <memory>
#include "set.h"

using namespace CMDR;

template<typename T>
class LockFreeList : public set<T> {

private:
	//list node
	class Node : public HazardMemory::Object {
	public:
		const T								m_item; //item stored in node
		AtomicMarkableReference<Node>		m_next; //next node in list

		Node(const T& item) : m_item(item), m_next(null, false) { }
		Node(const T& item, Node* const next, const bool mark) : m_item(item), m_next(next, mark) { }

		virtual ~Node() {;}

		virtual bool isValid() { return (false == m_next.isMarked()); }
		virtual HazardMemory::Object* getNextValid(const int indx) {
			return m_next.getReference();
		}
		virtual HazardMemory::Object* getNextValid(const int indx, int& flag) {
			bool mark;
			HazardMemory::Object* ptr = m_next.get(&mark);
			if(mark) 
				flag = 1; 
			else 
				flag=0;
			return ptr;
		}
	};

private:

	VolatileType<Node*>				m_head; // First list node
	SnapshotCounter					m_counter; //counter for number of element in the list

public:

	LockFreeList(int numOfThreads) : m_counter(numOfThreads) {
		printf("\n\tSet Is: Lock Free List\n");

		// Add sentinels to start and end
		m_head = new Node(Integer::MIN_VALUE, null, false);
		Node* tail = new Node(Integer::MAX_VALUE);
		m_head->m_next.set(tail,false);
	}

	//desctructor - removes all list elements
	~LockFreeList() {
		//we assume no one access the object at this point.
		Node* curr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != curr) {
			next = curr->m_next.getReference();
			delete curr;
			curr = next;
		}
	}

	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;

		while(true) {
			// find predecessor and current entries
			find(item, pred, curr, threadID);

			// is the key present?
			if (curr->m_item == item) {
				//element already in list - nothing to add
				return false;
			} else {
				// add new node to list
				std::auto_ptr<Node> node(new Node(item, curr.getReference() , false));
				if (pred->m_next.compareAndSet(curr.getReference(), node.get(), false, false)) {
					node.release();

					//element added successfully - increment number of element in list
					m_counter.inc(threadID);

					return true;
					}
			}
		}
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;

		while (true) {
			// find predecessor and current entries
			find(item, pred, curr, threadID);

			// is the key present?
			if (curr->m_item != item) {
				//element is not in list - nothing to remove
				return false;
			} else {
				// snip out matching node
				HazardMemory::Ptr<Node> succ;
				succ.extractNext(curr, 0);
				bool snip = curr->m_next.attemptMark(succ.getReference(), true);
				if (!snip)
					continue;

				//lets give it one shot
				snip = pred->m_next.compareAndSet(curr.getReference(), succ.getReference(), false, false);

				if (snip){
					//retire node - will be acctually deleted when not used anymore 
					curr.retire();

					//removed successfully - decrement number of element in list
					m_counter.dec(threadID);
				}

				return true;
			}
		}
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;

		// find predecessor and current entries
		find(item, pred, curr, threadID);

		//return true iff element found in list
		return (curr->m_item == item);
	}

	void clean(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
	
		head = m_head;
		curr.extractNext(head,0);
		bool snip;

		//remove each and every element from  the list
		while (true) {
			if (curr->m_item >= Integer::MAX_VALUE)
				return;

			succ.extractNext(curr,  0); 

			//try to delete
			snip = head->m_next.compareAndSet(curr.getReference(), succ.getReference(), false, false);

			if (snip){
				//retire node - will be acctually deleted when not used anymore 
				curr.retire();

				curr.extractNext(head,0);

				//removed successfully - decrement number of element in list
				m_counter.dec(threadID);
			}
		}
	}
	
	bool isEmpty(int threadID) {
		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
		
		int isMarked;	

		curr = m_head;

		//search for an element in the list that wasn't logically deleted
		while (curr->m_item < Integer::MAX_VALUE){
			succ.extractNext(curr, isMarked, 0);

			//make sure not logically deleted
			if (1==isMarked)
				return false;

			curr=succ;
		}

		return true;
	}
	
	int size(int threadID){
		return m_counter.scan();
	}

private:

	/*
	 * If element is present, returns node and predecessor. If absent, returns
	 * node with least larger key.
	 */
	void find(const T& item, HazardMemory::Ptr<Node>& pred, HazardMemory::Ptr<Node>& curr, int threadID) {
		HazardMemory::Ptr<Node> succ;

		while (true) {
			pred = m_head;
			curr.extractNext(pred,0);
			while (true) {
				int isMarked;
				succ.extractNext(curr, isMarked, 0); 

				//delete marked element
				if(1==isMarked) {

					//try to delete
					const bool snip = pred->m_next.compareAndSet(curr.getReference(), succ.getReference(), false, false);
					if (!snip)
						break;

					//retire node - will be acctually deleted when not used anymore 
					curr.retire();

					//removed successfully - decrement number of element in list
					m_counter.dec(threadID);
					curr = succ;
				} else {
					if (curr->m_item >= item)
						return;
					pred = curr;
					curr = succ;
				}
			}
		}
	}
};

#endif // __LOCK_FREE_LIST__H 
